import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description: 给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。
 * 例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)
 * User: 86187
 * Date: 2022-10-07
 * Time: 10:36
 */
public class TopK {

    public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if(input == null || k <= 0 || k > input.length){
            return list;
        }
        //按照数值从大到小
        PriorityQueue<Integer> queue = new PriorityQueue<>(k,new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                //return o1 - o2; //小堆
                return o2 - o1; //大堆
            }
        });
        for(int i = 0; i < input.length ; i++){
            if(i < k){
                queue.offer(input[i]);//前提前插入k个数据，queue会自动排序

            }else{
                //否则，就要展开淘汰的过程了，每次都淘汰最大的，剩下的最终就是最小的k个
                if(!queue.isEmpty() && input[i] < queue.peek()){ //input[i]比最大的小，跟新之
                    queue.poll();
                    queue.offer(input[i]);
                }
            }
        }
        //返回对应的结果
        for(int i = 0 ; i < k; i++){
            list.add(queue.poll());
        }
        Collections.sort(list);
        return list;
    }

    public static void main(String[] args) {
        Random random = new Random();
        int[] input = new int[20];
        int k = 5;
        for(int i = 0; i < input.length; ++i) {
            input[i] = random.nextInt(200)+1; // [1,200]
        }
        System.out.println(Arrays.toString(input));
        System.out.println(GetLeastNumbers_Solution(input, k));
    }
}
